First, I created a window which shows a sudoku:
<Window x:Class="SudokuSolver.SudokuShowWindow"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
Title="SudokuShowWindow" Height="550" Width="550">
<Grid Name="Grid1" HorizontalAlignment="Center" VerticalAlignment="Center">
<Grid.ColumnDefinitions>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
<ColumnDefinition Width="50"></ColumnDefinition>
</Grid.ColumnDefinitions>
<Grid.RowDefinitions>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
<RowDefinition Height="50"></RowDefinition>
</Grid.RowDefinitions>
</Grid>
</Window>And the corresponding code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Shapes;
namespace SudokuSolver
{
/// <summary>
/// Interaktionslogik für SudokuShowWindow.xaml
/// </summary>
public partial class SudokuShowWindow : Window
{
public SudokuShowWindow()
{
InitializeComponent();
}
public int[] numbers;
public TextBlock[] TextBlocks;
public void refreshValues(int[] _numbers)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (_numbers[i * 9 + j] != numbers[i * 9 + j])
{
TextBlocks[i * 9 + j].Text = _numbers[i * 9 + j].ToString();
}
}
}
}
public static SudokuShowWindow newSudokuShowWindow(int[] numbers)
{
SudokuShowWindow window = new SudokuShowWindow();
window.numbers = new int[81];
window.TextBlocks = new TextBlock[81];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
window.numbers[i * 9 + j] = numbers[i * 9 + j];
TextBlock tb = new TextBlock();
tb.Text = numbers[i * 9 + j].ToString();
tb.HorizontalAlignment = HorizontalAlignment.Center;
tb.VerticalAlignment = VerticalAlignment.Center;
Grid.SetRow(tb, i);
Grid.SetColumn(tb, j);
Thickness thk = new Thickness(0, 0, 0, 0);
if (i == 2 || i == 5)
{
thk.Bottom = 1;
}
if (i == 3 || i == 6)
{
thk.Top = 1;
}
if (j == 2 || j == 5)
{
thk.Right = 1;
}
if (j == 3 || j == 6)
{
thk.Left = 1;
}
Border border = new Border();
border.BorderThickness = thk;
border.BorderBrush = Brushes.Black;
Grid.SetRow(border, i);
Grid.SetColumn(border, j);
window.Grid1.Children.Add(border);
window.Grid1.Children.Add(tb);
window.TextBlocks[i * 9 + j] = tb;
}
}
window.Show();
return window;
}
}
}
This is now used to show the sudoku. The solver shows the actual sudoku and opens a new window for every found solution. MainWindow is empty, it is just used to start the program.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
namespace SudokuSolver
{
/// <summary>
/// Interaktionslogik für MainWindow.xaml
/// </summary>
public partial class MainWindow : Window
{
public MainWindow()
{
InitializeComponent();
Thread thread = new Thread(workLoop);
thread.Start();
}
private SudokuShowWindow window;
private int numberCounter;
private int[] initialNumbers;
private int[] numbers;
List<int[]> Solutions = new List<int[]>();
private void workLoop()
{
//The initial Sudoku which should be solved
initialNumbers = new int[81]
{
5,3,0, 0,7,0, 0,0,0,
6,0,0, 1,9,5, 0,0,0,
0,9,8, 0,0,0, 0,6,0,
8,0,0, 0,6,0, 0,0,3,
4,0,0, 8,0,3, 0,0,1,
7,0,0, 0,2,0, 0,0,6,
0,6,0, 0,0,0, 2,8,0,
0,0,0, 4,1,9, 0,0,5,
0,0,0, 0,8,0, 0,7,9
};
numbers = new int[81];
for (int i = 0; i < 81; i++)
{
numbers[i] = 0;
}
//Invoke window actions because we are not in the main thread
Application.Current.Dispatcher.BeginInvoke(new Action(() =>
{
window = SudokuShowWindow.newSudokuShowWindow(initialNumbers);
}));
//Position of the "cursor" in the sudoku
numberCounter = 0;
int ctr = 0;
bool noi = false;
while (true)
{
if (isItValid())
{
noi = false;
//A valid solution!
if (numberCounter > 80)
{
int[] totalNumbers = new int[81];
for (int i = 0; i < 81; i++)
{
totalNumbers[i] = initialNumbers[i];
if (totalNumbers[i] == 0)
{
totalNumbers[i] = numbers[i];
}
}
bool eq = false;
foreach (int[] solution in Solutions)
{
bool leq = true;
for (int i = 0; i < 81; i++)
{
if (solution[i] != totalNumbers[i])
{
leq = false;
}
}
if (leq)
{
eq = true;
}
}
if (!eq)
{
int[] tmp = new int[81];
for (int i = 0; i < 81; i++)
{
tmp[i] = totalNumbers[i];
}
Solutions.Add(tmp);
}
else
{
System.Console.WriteLine("Done!");
break;
}
Application.Current.Dispatcher.BeginInvoke(new Action(() =>
{
SudokuShowWindow.newSudokuShowWindow(totalNumbers);
}));
//Check for other solutions?
noi = true;
while (true)
{
numberCounter--;
if (initialNumbers[numberCounter] == 0)
{
if (numbers[numberCounter] >= 9)
{
numbers[numberCounter] = 0;
}
else
{
numbers[numberCounter]++;
break;
}
}
}
}
if (numberCounter > 80)
{
break;
}
if (numbers[numberCounter] == 0 && initialNumbers[numberCounter] == 0)
{
iterateOne();
}
else
{
if (!noi)
{
increaseNumberCounter();
}
}
}
else
{
if (numberCounter > 80 || numberCounter < 0)
{
break;
}
if (numbers[numberCounter] >= 9)
{
decreaseOne();
Application.Current.Dispatcher.BeginInvoke(new Action(() =>
{
int[] totalNumbers = new int[81];
for (int i = 0; i < 81; i++)
{
totalNumbers[i] = initialNumbers[i];
if (totalNumbers[i] == 0)
{
totalNumbers[i] = numbers[i];
}
}
window.refreshValues(totalNumbers);
}));
}
else
{
iterateOne();
}
}
ctr++;
if (ctr > 1000)
{
ctr = 0;
Application.Current.Dispatcher.BeginInvoke(new Action(() =>
{
int[] totalNumbers = new int[81];
for (int i = 0; i < 81; i++)
{
totalNumbers[i] = initialNumbers[i];
if (totalNumbers[i] == 0)
{
totalNumbers[i] = numbers[i];
}
}
window.refreshValues(totalNumbers);
}));
Thread.Sleep(1);
}
}
Application.Current.Dispatcher.BeginInvoke(new Action(() =>
{
window.Close();
}));
}
void increaseNumberCounter()
{
numberCounter++;
while (numberCounter <= 80 && initialNumbers[numberCounter] != 0)
{
numberCounter++;
}
}
void iterateOne()
{
if (numberCounter > 80)
{
return;
}
while (initialNumbers[numberCounter] != 0)
{
numberCounter++;
}
numbers[numberCounter]++;
}
void decreaseOne()
{
if (numberCounter > 80)
{
numberCounter = 80;
}
numbers[numberCounter] = 0;
if (numberCounter == 0)
{
return;
}
while (numberCounter >= 0)
{
numberCounter--;
while (numberCounter > 0 && initialNumbers[numberCounter] != 0)
{
numberCounter--;
}
if (numberCounter < 0)
{
return;
}
if (numbers[numberCounter] < 9)
{
numbers[numberCounter]++;
return;
}
else
{
numbers[numberCounter] = 0;
}
}
}
bool isItValid()
{
int[] totalNumbers = new int[81];
for (int i = 0; i < 81; i++)
{
totalNumbers[i] = initialNumbers[i];
if (totalNumbers[i] == 0)
{
totalNumbers[i] = numbers[i];
}
}
//Check Horizontal
List<int> testList;
for (int i = 0; i < 9; i++)
{
testList = new List<int>();
for (int j = 0; j < 9; j++)
{
if (testList.Contains(totalNumbers[i * 9 + j]))
{
//Invalid
return false;
}
if (totalNumbers[i * 9 + j] != 0)
{
testList.Add(totalNumbers[i * 9 + j]);
}
}
}
//Check Vertical
for (int j = 0; j < 9; j++)
{
testList = new List<int>();
for (int i = 0; i < 9; i++)
{
if (testList.Contains(totalNumbers[i * 9 + j]))
{
//Invalid
return false;
}
if (totalNumbers[i * 9 + j] != 0)
{
testList.Add(totalNumbers[i * 9 + j]);
}
}
}
//Check squares
for (int ii = 0; ii < 3; ii++)
{
for (int jj = 0; jj < 3; jj++)
{
testList = new List<int>();
for (int i = ii * 3; i < ii * 3 + 3; i++)
{
for (int j = jj * 3; j < jj * 3 + 3; j++)
{
if (testList.Contains(totalNumbers[i * 9 + j]))
{
//Invalid
return false;
}
if (totalNumbers[i * 9 + j] != 0)
{
testList.Add(totalNumbers[i * 9 + j]);
}
}
}
}
}
//Valid
return true;
}
}
}
No comments:
Post a Comment