The sudoku-kata from zoran-horvat

The solving code needs to know the solution, in order to solve the grid

Background

Thanks for this kata - I was intrigued enough to try adding tests and doing some refactoring, as the first C# code I've ever written!!! Coming from C++, I was really happy with how much progress I made...

Anyway, I'm writing this up in case anyone else saw the webinar recording "Refactoring a 1000-Line Method into Clean(er) Code", and was intrigued to see if they could add tests, or even refactor the code to use the solver to solve Sudoku puzzles from newspapers or whatever...

I'm certainly not suggesting that it be fixed - I just wanted to share what I'd learned, in case others come here with a simliar idea.

Observation: The region "Final attempt - look if the board has multiple solutions" needs the actual solution in order to guess what digits to use.

This us that region:

sudoku-kata/SudokuKata/SudokuKata/Program.cs

Lines 680 to 975 in c0c3e09

 #region Final attempt - look if the board has multiple solutions 

 if (!changeMade) 

 { 

 // This is the last chance to do something in this iteration: 

 // If this attempt fails, board will not be entirely solved. 

 // Try to see if there are pairs of values that can be exchanged arbitrarily 

 // This happens when board has more than one valid solution 

 Queue<int> candidateIndex1 = new Queue<int>(); 

 Queue<int> candidateIndex2 = new Queue<int>(); 

 Queue<int> candidateDigit1 = new Queue<int>(); 

 Queue<int> candidateDigit2 = new Queue<int>(); 

 for (int i = 0; i < candidateMasks.Length - 1; i++) 

 { 

 if (maskToOnesCount[candidateMasks[i]] == 2) 

 { 

 int row = i / 9; 

 int col = i % 9; 

 int blockIndex = 3 * (row / 3) + col / 3; 

 int temp = candidateMasks[i]; 

 int lower = 0; 

 int upper = 0; 

 for (int digit = 1; temp > 0; digit++) 

 { 

 if ((temp & 1) != 0) 

 { 

 lower = upper; 

 upper = digit; 

 } 

 temp = temp >> 1; 

 } 

 for (int j = i + 1; j < candidateMasks.Length; j++) 

 { 

 if (candidateMasks[j] == candidateMasks[i]) 

 { 

 int row1 = j / 9; 

 int col1 = j % 9; 

 int blockIndex1 = 3 * (row1 / 3) + col1 / 3; 

 if (row == row1 || col == col1 || blockIndex == blockIndex1) 

 { 

 candidateIndex1.Enqueue(i); 

 candidateIndex2.Enqueue(j); 

 candidateDigit1.Enqueue(lower); 

 candidateDigit2.Enqueue(upper); 

 } 

 } 

 } 

 } 

 } 

 // At this point we have the lists with pairs of cells that might pick one of two digits each 

 // Now we have to check whether that is really true - does the board have two solutions? 

 List<int> stateIndex1 = new List<int>(); 

 List<int> stateIndex2 = new List<int>(); 

 List<int> value1 = new List<int>(); 

 List<int> value2 = new List<int>(); 

 while (candidateIndex1.Any()) 

 { 

 int index1 = candidateIndex1.Dequeue(); 

 int index2 = candidateIndex2.Dequeue(); 

 int digit1 = candidateDigit1.Dequeue(); 

 int digit2 = candidateDigit2.Dequeue(); 

 int[] alternateState = new int[finalState.Length]; 

 Array.Copy(state, alternateState, alternateState.Length); 

 if (finalState[index1] == digit1) 

 { 

 alternateState[index1] = digit2; 

 alternateState[index2] = digit1; 

 } 

 else 

 { 

 alternateState[index1] = digit1; 

 alternateState[index2] = digit2; 

 } 

 // What follows below is a complete copy-paste of the solver which appears at the beginning of this method 

 // However, the algorithm couldn't be applied directly and it had to be modified. 

 // Implementation below assumes that the board might not have a solution. 

 stateStack = new Stack<int[]>(); 

 rowIndexStack = new Stack<int>(); 

 colIndexStack = new Stack<int>(); 

 usedDigitsStack = new Stack<bool[]>(); 

 lastDigitStack = new Stack<int>(); 

 command = "expand"; 

 while (command != "complete" && command != "fail") 

 { 

 if (command == "expand") 

 { 

 int[] currentState = new int[9 * 9]; 

 if (stateStack.Any()) 

 { 

 Array.Copy(stateStack.Peek(), currentState, currentState.Length); 

 } 

 else 

 { 

 Array.Copy(alternateState, currentState, currentState.Length); 

 } 

 int bestRow = -1; 

 int bestCol = -1; 

 bool[] bestUsedDigits = null; 

 int bestCandidatesCount = -1; 

 int bestRandomValue = -1; 

 bool containsUnsolvableCells = false; 

 for (int index = 0; index < currentState.Length; index++) 

 if (currentState[index] == 0) 

 { 

 int row = index / 9; 

 int col = index % 9; 

 int blockRow = row / 3; 

 int blockCol = col / 3; 

 bool[] isDigitUsed = new bool[9]; 

 for (int i = 0; i < 9; i++) 

 { 

 int rowDigit = currentState[9 * i + col]; 

 if (rowDigit > 0) 

 isDigitUsed[rowDigit - 1] = true; 

 int colDigit = currentState[9 * row + i]; 

 if (colDigit > 0) 

 isDigitUsed[colDigit - 1] = true; 

 int blockDigit = currentState[(blockRow * 3 + i / 3) * 9 + (blockCol * 3 + i % 3)]; 

 if (blockDigit > 0) 

 isDigitUsed[blockDigit - 1] = true; 

 } // for (i = 0..8) 

 int candidatesCount = isDigitUsed.Where(used => !used).Count(); 

 if (candidatesCount == 0) 

 { 

 containsUnsolvableCells = true; 

 break; 

 } 

 int randomValue = rng.Next(); 

 if (bestCandidatesCount < 0 || 

 candidatesCount < bestCandidatesCount || 

 (candidatesCount == bestCandidatesCount && randomValue < bestRandomValue)) 

 { 

 bestRow = row; 

 bestCol = col; 

 bestUsedDigits = isDigitUsed; 

 bestCandidatesCount = candidatesCount; 

 bestRandomValue = randomValue; 

 } 

 } // for (index = 0..81) 

 if (!containsUnsolvableCells) 

 { 

 stateStack.Push(currentState); 

 rowIndexStack.Push(bestRow); 

 colIndexStack.Push(bestCol); 

 usedDigitsStack.Push(bestUsedDigits); 

 lastDigitStack.Push(0); // No digit was tried at this position 

 } 

 // Always try to move after expand 

 command = "move"; 

 } // if (command == "expand") 

 else if (command == "collapse") 

 { 

 stateStack.Pop(); 

 rowIndexStack.Pop(); 

 colIndexStack.Pop(); 

 usedDigitsStack.Pop(); 

 lastDigitStack.Pop(); 

 if (stateStack.Any()) 

 command = "move"; // Always try to move after collapse 

 else 

 command = "fail"; 

 } 

 else if (command == "move") 

 { 

 int rowToMove = rowIndexStack.Peek(); 

 int colToMove = colIndexStack.Peek(); 

 int digitToMove = lastDigitStack.Pop(); 

 int rowToWrite = rowToMove + rowToMove / 3 + 1; 

 int colToWrite = colToMove + colToMove / 3 + 1; 

 bool[] usedDigits = usedDigitsStack.Peek(); 

 int[] currentState = stateStack.Peek(); 

 int currentStateIndex = 9 * rowToMove + colToMove; 

 int movedToDigit = digitToMove + 1; 

 while (movedToDigit <= 9 && usedDigits[movedToDigit - 1]) 

 movedToDigit += 1; 

 if (digitToMove > 0) 

 { 

 usedDigits[digitToMove - 1] = false; 

 currentState[currentStateIndex] = 0; 

 board[rowToWrite][colToWrite] = '.'; 

 } 

 if (movedToDigit <= 9) 

 { 

 lastDigitStack.Push(movedToDigit); 

 usedDigits[movedToDigit - 1] = true; 

 currentState[currentStateIndex] = movedToDigit; 

 board[rowToWrite][colToWrite] = (char)('0' + movedToDigit); 

 if (currentState.Any(digit => digit == 0)) 

 command = "expand"; 

 else 

 command = "complete"; 

 } 

 else 

 { 

 // No viable candidate was found at current position - pop it in the next iteration 

 lastDigitStack.Push(0); 

 command = "collapse"; 

 } 

 } // if (command == "move") 

 } // while (command != "complete" && command != "fail") 

 if (command == "complete") 

 { // Board was solved successfully even with two digits swapped 

 stateIndex1.Add(index1); 

 stateIndex2.Add(index2); 

 value1.Add(digit1); 

 value2.Add(digit2); 

 } 

 } // while (candidateIndex1.Any()) 

 if (stateIndex1.Any()) 

 { 

 int pos = rng.Next(stateIndex1.Count()); 

 int index1 = stateIndex1.ElementAt(pos); 

 int index2 = stateIndex2.ElementAt(pos); 

 int digit1 = value1.ElementAt(pos); 

 int digit2 = value2.ElementAt(pos); 

 int row1 = index1 / 9; 

 int col1 = index1 % 9; 

 int row2 = index2 / 9; 

 int col2 = index2 % 9; 

 string description = string.Empty; 

 if (index1 / 9 == index2 / 9) 

 { 

 description = $"row #{index1 / 9 + 1}"; 

 } 

 else if (index1 % 9 == index2 % 9) 

 { 

 description = $"column #{index1 % 9 + 1}"; 

 } 

 else 

 { 

 description = $"block ({row1 / 3 + 1}, {col1 / 3 + 1})"; 

 } 

 state[index1] = finalState[index1]; 

 state[index2] = finalState[index2]; 

 candidateMasks[index1] = 0; 

 candidateMasks[index2] = 0; 

 changeMade = true; 

 for (int i = 0; i < state.Length; i++) 

 { 

 int tempRow = i / 9; 

 int tempCol = i % 9; 

 int rowToWrite = tempRow + tempRow / 3 + 1; 

 int colToWrite = tempCol + tempCol / 3 + 1; 

 board[rowToWrite][colToWrite] = '.'; 

 if (state[i] > 0) 

 board[rowToWrite][colToWrite] = (char)('0' + state[i]); 

 } 

 Console.WriteLine($"Guessing that {digit1} and {digit2} are arbitrary in {description} (multiple solutions): Pick {finalState[index1]}->({row1 + 1}, {col1 + 1}), {finalState[index2]}->({row2 + 1}, {col2 + 1})."); 

 } 

 } 

 #endregion

This is because that region makes several uses of finalState, which is a copy of the starting, fully-populated state. The copy is made here:

sudoku-kata/SudokuKata/SudokuKata/Program.cs

Lines 202 to 205 in c0c3e09

 int[] state = stateStack.Peek(); 

 int[] finalState = new int[state.Length]; 

 Array.Copy(state, finalState, finalState.Length);

zoran-horvat / sudoku-kata Goto Github PK

sudoku-kata's People

Stargazers

Watchers

Forkers

sudoku-kata's Issues

The solving code needs to know the solution, in order to solve the grid

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	#region Final attempt - look if the board has multiple solutions
	if (!changeMade)
	{
	// This is the last chance to do something in this iteration:
	// If this attempt fails, board will not be entirely solved.

	// Try to see if there are pairs of values that can be exchanged arbitrarily
	// This happens when board has more than one valid solution

	Queue<int> candidateIndex1 = new Queue<int>();
	Queue<int> candidateIndex2 = new Queue<int>();
	Queue<int> candidateDigit1 = new Queue<int>();
	Queue<int> candidateDigit2 = new Queue<int>();

	for (int i = 0; i < candidateMasks.Length - 1; i++)
	{
	if (maskToOnesCount[candidateMasks[i]] == 2)
	{
	int row = i / 9;
	int col = i % 9;
	int blockIndex = 3 * (row / 3) + col / 3;

	int temp = candidateMasks[i];
	int lower = 0;
	int upper = 0;
	for (int digit = 1; temp > 0; digit++)
	{
	if ((temp & 1) != 0)
	{
	lower = upper;
	upper = digit;
	}
	temp = temp >> 1;
	}

	for (int j = i + 1; j < candidateMasks.Length; j++)
	{
	if (candidateMasks[j] == candidateMasks[i])
	{
	int row1 = j / 9;
	int col1 = j % 9;
	int blockIndex1 = 3 * (row1 / 3) + col1 / 3;

	if (row == row1 \|\| col == col1 \|\| blockIndex == blockIndex1)
	{
	candidateIndex1.Enqueue(i);
	candidateIndex2.Enqueue(j);
	candidateDigit1.Enqueue(lower);
	candidateDigit2.Enqueue(upper);
	}
	}
	}
	}
	}

	// At this point we have the lists with pairs of cells that might pick one of two digits each
	// Now we have to check whether that is really true - does the board have two solutions?

	List<int> stateIndex1 = new List<int>();
	List<int> stateIndex2 = new List<int>();
	List<int> value1 = new List<int>();
	List<int> value2 = new List<int>();

	while (candidateIndex1.Any())
	{
	int index1 = candidateIndex1.Dequeue();
	int index2 = candidateIndex2.Dequeue();
	int digit1 = candidateDigit1.Dequeue();
	int digit2 = candidateDigit2.Dequeue();

	int[] alternateState = new int[finalState.Length];
	Array.Copy(state, alternateState, alternateState.Length);

	if (finalState[index1] == digit1)
	{
	alternateState[index1] = digit2;
	alternateState[index2] = digit1;
	}
	else
	{
	alternateState[index1] = digit1;
	alternateState[index2] = digit2;
	}

	// What follows below is a complete copy-paste of the solver which appears at the beginning of this method
	// However, the algorithm couldn't be applied directly and it had to be modified.
	// Implementation below assumes that the board might not have a solution.
	stateStack = new Stack<int[]>();
	rowIndexStack = new Stack<int>();
	colIndexStack = new Stack<int>();
	usedDigitsStack = new Stack<bool[]>();
	lastDigitStack = new Stack<int>();

	command = "expand";
	while (command != "complete" && command != "fail")
	{
	if (command == "expand")
	{
	int[] currentState = new int[9 * 9];

	if (stateStack.Any())
	{
	Array.Copy(stateStack.Peek(), currentState, currentState.Length);
	}
	else
	{
	Array.Copy(alternateState, currentState, currentState.Length);
	}

	int bestRow = -1;
	int bestCol = -1;
	bool[] bestUsedDigits = null;
	int bestCandidatesCount = -1;
	int bestRandomValue = -1;
	bool containsUnsolvableCells = false;

	for (int index = 0; index < currentState.Length; index++)
	if (currentState[index] == 0)
	{

	int row = index / 9;
	int col = index % 9;
	int blockRow = row / 3;
	int blockCol = col / 3;

	bool[] isDigitUsed = new bool[9];

	for (int i = 0; i < 9; i++)
	{
	int rowDigit = currentState[9 * i + col];
	if (rowDigit > 0)
	isDigitUsed[rowDigit - 1] = true;

	int colDigit = currentState[9 * row + i];
	if (colDigit > 0)
	isDigitUsed[colDigit - 1] = true;

	int blockDigit = currentState[(blockRow * 3 + i / 3) * 9 + (blockCol * 3 + i % 3)];
	if (blockDigit > 0)
	isDigitUsed[blockDigit - 1] = true;
	} // for (i = 0..8)

	int candidatesCount = isDigitUsed.Where(used => !used).Count();

	if (candidatesCount == 0)
	{
	containsUnsolvableCells = true;
	break;
	}

	int randomValue = rng.Next();

	if (bestCandidatesCount < 0 \|\|
	candidatesCount < bestCandidatesCount \|\|
	(candidatesCount == bestCandidatesCount && randomValue < bestRandomValue))
	{
	bestRow = row;
	bestCol = col;
	bestUsedDigits = isDigitUsed;
	bestCandidatesCount = candidatesCount;
	bestRandomValue = randomValue;
	}

	} // for (index = 0..81)

	if (!containsUnsolvableCells)
	{
	stateStack.Push(currentState);
	rowIndexStack.Push(bestRow);
	colIndexStack.Push(bestCol);
	usedDigitsStack.Push(bestUsedDigits);
	lastDigitStack.Push(0); // No digit was tried at this position
	}

	// Always try to move after expand
	command = "move";

	} // if (command == "expand")
	else if (command == "collapse")
	{
	stateStack.Pop();
	rowIndexStack.Pop();
	colIndexStack.Pop();
	usedDigitsStack.Pop();
	lastDigitStack.Pop();

	if (stateStack.Any())
	command = "move"; // Always try to move after collapse
	else
	command = "fail";
	}
	else if (command == "move")
	{

	int rowToMove = rowIndexStack.Peek();
	int colToMove = colIndexStack.Peek();
	int digitToMove = lastDigitStack.Pop();

	int rowToWrite = rowToMove + rowToMove / 3 + 1;
	int colToWrite = colToMove + colToMove / 3 + 1;

	bool[] usedDigits = usedDigitsStack.Peek();
	int[] currentState = stateStack.Peek();
	int currentStateIndex = 9 * rowToMove + colToMove;

	int movedToDigit = digitToMove + 1;
	while (movedToDigit <= 9 && usedDigits[movedToDigit - 1])
	movedToDigit += 1;

	if (digitToMove > 0)
	{
	usedDigits[digitToMove - 1] = false;
	currentState[currentStateIndex] = 0;
	board[rowToWrite][colToWrite] = '.';
	}

	if (movedToDigit <= 9)
	{
	lastDigitStack.Push(movedToDigit);
	usedDigits[movedToDigit - 1] = true;
	currentState[currentStateIndex] = movedToDigit;
	board[rowToWrite][colToWrite] = (char)('0' + movedToDigit);

	if (currentState.Any(digit => digit == 0))
	command = "expand";
	else
	command = "complete";
	}
	else
	{
	// No viable candidate was found at current position - pop it in the next iteration
	lastDigitStack.Push(0);
	command = "collapse";
	}
	} // if (command == "move")

	} // while (command != "complete" && command != "fail")

	if (command == "complete")
	{ // Board was solved successfully even with two digits swapped
	stateIndex1.Add(index1);
	stateIndex2.Add(index2);
	value1.Add(digit1);
	value2.Add(digit2);
	}
	} // while (candidateIndex1.Any())

	if (stateIndex1.Any())
	{
	int pos = rng.Next(stateIndex1.Count());
	int index1 = stateIndex1.ElementAt(pos);
	int index2 = stateIndex2.ElementAt(pos);
	int digit1 = value1.ElementAt(pos);
	int digit2 = value2.ElementAt(pos);
	int row1 = index1 / 9;
	int col1 = index1 % 9;
	int row2 = index2 / 9;
	int col2 = index2 % 9;

	string description = string.Empty;

	if (index1 / 9 == index2 / 9)
	{
	description = $"row #{index1 / 9 + 1}";
	}
	else if (index1 % 9 == index2 % 9)
	{
	description = $"column #{index1 % 9 + 1}";
	}
	else
	{
	description = $"block ({row1 / 3 + 1}, {col1 / 3 + 1})";
	}

	state[index1] = finalState[index1];
	state[index2] = finalState[index2];
	candidateMasks[index1] = 0;
	candidateMasks[index2] = 0;
	changeMade = true;

	for (int i = 0; i < state.Length; i++)
	{
	int tempRow = i / 9;
	int tempCol = i % 9;
	int rowToWrite = tempRow + tempRow / 3 + 1;
	int colToWrite = tempCol + tempCol / 3 + 1;

	board[rowToWrite][colToWrite] = '.';
	if (state[i] > 0)
	board[rowToWrite][colToWrite] = (char)('0' + state[i]);
	}

	Console.WriteLine($"Guessing that {digit1} and {digit2} are arbitrary in {description} (multiple solutions): Pick {finalState[index1]}->({row1 + 1}, {col1 + 1}), {finalState[index2]}->({row2 + 1}, {col2 + 1}).");
	}
	}
	#endregion

	int[] state = stateStack.Peek();

	int[] finalState = new int[state.Length];
	Array.Copy(state, finalState, finalState.Length);